#include <iostream>
#include <vector>
/*
基于递归的二分搜索算法
*/
int binary_search(std::vector<int> &v, int left, int right, int target) {
  if (left > right)
    return -1;
  int mid = (left + right) / 2;
  if (v[mid] < target) {
    return binary_search(v, mid + 1, right, target);
  } else if (v[mid] > target) {
    return binary_search(v, left, mid - 1, target);
  } else {
    return mid;
  }
}

int main() {
  std::vector<int> list{1, 2, 3, 4, 5, 6, 7, 8, 9};
  int pos = binary_search(list, 0, list.size() - 1, 5);
  std::cout << pos << std::endl;
}